import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

/*
 * Classe de controle, que possui todos os metodos necessarios para se encontrar uma solucao, sua vizinhanca, etc
 */
public class Control {
	private List<String> usedTowers;
	private List<String> solution;
	private List<String> notUsedTowers;
	private Double solutionCost;
	private Integer[] pointsCovered;
	private Map<String, Tower> towersMap;
	private Integer solutionCount;
	private Double initialSolutionCost;
	private Integer nPoints;
	private Integer towerNumbers;
	private List<List<String>> localInitSolutions;
	private List<String> globalSolution;
	private Double globalSolutionCost;

	/*
	 * Construtor da classe, seta:
	 * - Lista de pontos cobertos pela solucao (necessario para verificar se esta é uma solucao valida)
	 * - Custo da solucao
	 * - Lista de torres utilizadas pela solucao
	 * - Lista de torres nao utilizadas pela solucao (necessario para realizar a permutacao, ao calcular a vizinhanca
	 * - Mapa de torres (necessario para se pegar uma torre a partir de seu nome)
	 * - Número total de torres
	 * - Contador de verificação (verifica se uma solução foi atingida com o conjunto atual de torres)
	 * - Lista com as soluções iniciais já encontradas (para que a solução inicial aleatória não seja repetida)
	 * - Custo global (ao final, será o melhor custo) e solução global (ao final será a melhor solução)
	 */
	public Control(final Integer nPoints, final List<Tower> towers, final Integer towerNumbers){
		this.pointsCovered = new Integer[nPoints+1];
		for (int i = 0; i <= nPoints; i++){
			this.pointsCovered[i] = 0;
		}
		this.nPoints = nPoints;
		this.solutionCost = 0.0;
		this.initialSolutionCost = 0.0;
		this.usedTowers = new ArrayList<String>();
		this.notUsedTowers = new ArrayList<String>();
		this.towersMap = new HashMap<String, Tower>();
		for (Tower t : towers){
			this.towersMap.put(t.getName(), t);
		}
		this.solutionCount = 0;
		this.towerNumbers = towerNumbers;
		this.localInitSolutions = new ArrayList<List<String>>();
		this.globalSolution = new ArrayList<String>();
		this.globalSolutionCost = 0.0;
	}

	/*
	 * Método que, ao final de cada iteração do método findNeighborhood, zera todas as variáveis necessárias, 
	 * para que não haja lixo acumulado
	 */
	private void reset(){
		this.usedTowers = new ArrayList<String>();
		this.notUsedTowers = new ArrayList<String>();
		for (int i = 0; i <= nPoints; i++){
			this.pointsCovered[i] = 0;
		}
		this.solutionCount = 0;
		this.solutionCost = 0.0;
		this.initialSolutionCost = 0.0;
		this.solution = null;
	}

	/*
	 * Método principal de busca. Durante 55 segundos, roda diversas buscas locais, com o intuito de
	 * "fugir" dos mínimos locais. Se o valor encontrado pela busca local atual é melhor do que os valores
	 * encontrados por todas as buscas locais anteriores, atualiza a solução global e o custo global.
	 * Isto garante que ao final de 55 segundos, teremos a melhor solução encontrada pela heurística na 
	 * solução global (isto é, a solução com menor custo, custo este que estará armazenado no custo global).
	 */
	public void globalSearch(){
		int interval = 55000; 
		Date initDate = new Date();
		Long initMillis = initDate.getTime();
		Date now = new Date();
		Long nowMillis = now.getTime();

		while(nowMillis - initMillis < interval){
			localSearch();
			/*
			 * Caso o custo da solução global seja 0 (iteração inicial) ou o custo encontrado pela busca local
			 * atual seja menor do que o custo encontrado por todas as outras buscas locais, atualiza a solução
			 * global, e o custo global
			 */
			if (globalSolutionCost == 0 || solutionCost < globalSolutionCost){
				globalSolution = (List<String>) ((ArrayList<String>)solution).clone();
				globalSolutionCost = solutionCost;
			}
			now = new Date();
			nowMillis = now.getTime();
		}
		System.out.println("Valor: " + globalSolutionCost);
		System.out.println("Total: " + globalSolution.size());
		for(String s : globalSolution){
			System.out.println(s);
		}
		
	}

	/*
	 * Método de busca local. Uma solução inicial é encontrada chamando-se o método findSolution. Após isso, calcula-se
	 * a vizinhança desta solução inicial, chamando-se o método findNeighborhood, que seta em 'solution' e 'solutionCost'
	 * o vizinho que possui menor custo. Após isso, seta-se este vizinho como sendo a nova 'solução inicial', e chama-se
	 * o método findNeighborhood novamente, até que a solução atual não possua nenhum vizinho com custo menor.
	 */
	private void localSearch(){
		findSolution(nPoints);

		localInitSolutions.add(usedTowers);
		
		/*
		 * Enquanto o custo da solução for zero (iteração inicial) e o custo da solução encontrada em findNeighborhood for
		 * menor que o custo da solução anterior, continua calculando a vizinhança da solução encontrada.
		 */
		while (solutionCost == 0.0 || solutionCost < initialSolutionCost){
			if (solutionCost != 0.0)
				initialSolutionCost = solutionCost;
			findNeighborhood();
			usedTowers = (List<String>) ((ArrayList<String>)solution).clone();
			notUsedTowers = findComplement(usedTowers);
		}
		
	}


	/*
	 * Metodo que acha uma solucao inicial (antes da etapa de busca local)
	 * Apos achar a solucao inicial, o metodo findNeighborhood é chamado, para que a vizinhanca
	 * desta solucao inicial seja determinada.
	 */
	private List<String> findSolution(final Integer nPoints){
		reset();
		while (solutionCount < nPoints){
			Random randomGenerator = new Random();
			Integer index = randomGenerator.nextInt(towerNumbers+1);
			String towerName = "S"+index.toString();
			while (usedTowers.contains(towerName) || index == 0){
				index = randomGenerator.nextInt(towerNumbers+1);
				towerName = "S"+index.toString();
			}
			Tower towerAux = towersMap.get(towerName);
			addTowerToSolution(towerAux);
		}
		notUsedTowers = findComplement(usedTowers);

		return this.usedTowers;
	}

	/* calcula complemento - torres nao utilizadas */
	private List<String> findComplement(List<String> used){
		List<String> notUsed = new ArrayList<String>();
		for(Integer i=1; i<=towerNumbers; i++){
			String nameAux = "S" + i.toString();
			if(!used.contains(nameAux))
				notUsed.add(nameAux);
		}

		return notUsed;
	}


	/*
	 * Metodo que verifica se vale a pena adicionar uma determinada torre a solucao
	 * Uma torre vale a pena ser adicionada caso ela possua algum ponto que ainda nao foi coberto
	 * pelas torres contidas na solucao atual. Caso contrario, ela nao é adicionada.
	 */
	private void addTowerToSolution(final Tower t){
		Boolean worthTower = Boolean.FALSE;
		for (Integer i : t.getCoveredPoints()){
			if (pointsCovered[i] == 0){
				worthTower = Boolean.TRUE;
				solutionCount++;
			}
			pointsCovered[i] = pointsCovered[i] + 1;
		}
		if (!worthTower){
			for (Integer i : t.getCoveredPoints()){
				pointsCovered[i] = pointsCovered[i] - 1;
			}
		}else{
			usedTowers.add(t.getName());
			initialSolutionCost += t.getCost();
		}
	}

	/*
	 * Metodo que calcula a vizinhanca de uma determinada solucao.
	 * A vizinhanca de uma solucao é definida como o conjunto de solucoes gerado a partir da permutacao de apenas
	 * um elemento (uma torre) da solucao atual.
	 * Por exemplo: Temos 6 torres, e uma solucao (T1, T2, T3, T4). Os conjuntos (T5, T2, T3, T4), (T6, T2, T3, T4), etc
	 * sao elementos da vizinhanca desta solucao.
	 */
	private void findNeighborhood(){
		Integer[] coveredAux = new Integer[pointsCovered.length];
		Double solutionCostAux = initialSolutionCost.doubleValue();

		solutionCost = initialSolutionCost.doubleValue();

		for(Integer k=0; k<coveredAux.length; k++)
			coveredAux[k] = pointsCovered[k];

		for(Integer i = 0; i < usedTowers.size(); i++){
			Integer solutionCountAux = solutionCount.intValue();
			solutionCostAux = initialSolutionCost.doubleValue();
			Tower t = towersMap.get(usedTowers.get(i));
			/* Para cada torre i presente na solucao, retiramos esta torre i, subtraimos seu custo
			 * do custo total, e retiramos os pontos cobertos pela mesma da lista de pontos cobertos
			 */
			solutionCostAux = solutionCostAux.doubleValue() - t.getCost().doubleValue();
			for(Integer l : t.getCoveredPoints()){
				coveredAux[l] = coveredAux[l] - 1;
				if(coveredAux[l] == 0){
					solutionCountAux--;
				}
			}

			for(Integer j=0; j<notUsedTowers.size(); j++){
				/* Para cada torre i retirada, adicionamos uma torre j (uma a cada iteracao) para 
				 * gerar um novo cojunto de torres, que pode ser ou nao uma solucao pertencente a vizinhanca
				 */
				ArrayList<String> neighboor = (ArrayList<String>) ((ArrayList<String>)usedTowers).clone();
				neighboor.set(i, notUsedTowers.get(j));
				Tower t2 = towersMap.get(notUsedTowers.get(j));
				/* Se o custo da torre j é menor do que o custo da torre i, ela vale a pena ser adicionada para
				 * gerar-se um novo conjunto de torres, pois o custo total do conjunto contendo a torre j é menor
				 * do que o custo total do conjunto contendo a torre i. Caso contrario, esta solucao nao é considerada.
				 */
				if (t2.getCost().doubleValue() < t.getCost().doubleValue()){
					for(Integer l : t2.getCoveredPoints()){
						coveredAux[l] = coveredAux[l] + 1;
						if(coveredAux[l] == 1)
							solutionCountAux++;
					}
					/* Caso a variavel solutionCountAux seja igual a nPoint, temos uma solucao valida (que cobre
					 * todos os pontos). Neste caso, como ja conferimos que seu custo total é menor do que o custo
					 * total da solucao anterior (contendo a torre i), atualizamos a solucao, e o seu respectivo custo
					 */
					if(solutionCountAux == nPoints && (solutionCostAux.doubleValue() + t2.getCost().doubleValue() < solutionCost)){
						solution = (ArrayList<String>) neighboor.clone();
						solutionCost = solutionCostAux.doubleValue() + t2.getCost().doubleValue();
					}
					/* Removemos os pontos cobertos pela torre j, para que a iteração possa continuar sem problemas */ 
					for(Integer l : t2.getCoveredPoints()){
						coveredAux[l] = coveredAux[l] - 1;
						if(coveredAux[l] == 0)
							solutionCountAux--;
					}	
				}
			}
			/* Adicionamos novamente os pontos cobertos pela torre i, para que a iteração possa continuar sem problemas */
			for(Integer l : t.getCoveredPoints()){
				coveredAux[l] = coveredAux[l] + 1;
				if(coveredAux[l] == 1)
					solutionCountAux++;
			}
		}
		/*
		 * Caso solution seja nulo, nenhum vizinho da primeira solução possui custo melhor. Portanto, o valor
		 * atribuído a 'solution' é o mesmo da solução inicial determinada.
		 */
		if (solution == null){
			solution = (List<String>) ((ArrayList<String>)usedTowers).clone();
		}

	}


}
